Various methods exist for displaying an inside portion of a structure. However, all of these methods are based on having three-dimensional knowledge of the structure to be studied. A structure is thus normally described by a collection of volume elements or "voxels", where each voxel represents firstly a position in three-dimensional space inside the structure, and secondly at least one physical magnitude value representative of the structure at this position. Depending on the fineness of the voxels, the image of the structure is said to be resolved more or less finely. In the medical field, the physical phenomenon concerned relates essentially to the mean radiological density of each voxel when the investigation includes passing a patient through a tomographic X-ray scanner. When a nuclear magnetic resonance apparatus is used, then the phenomenon relates essentially in measuring the hydrogen content of each voxel. For an ultrasonic scan, the ability of each voxel at backscanning sound waves is measured. When measurements are performed by means of a gamma camera, then it is essentially metabolic functions that are measured in conjunction with a radiographic marker. Other investigative procedures may also be considered. The invention relates to all investigative procedures that give rise to knowledge of at least one physical magnitude in each voxel of the structure.
In the image processing with which the present invention is concerned, each voxel is associated with a memory word in a memory. The memory represents the structure. The addresses of memory words in the memory correspond to the positions occupied by the voxels in three-dimensional space. The information stored in each memory word represents the value(s) of physical magnitude(s) measured at the position of the corresponding voxel. In the description below, such a memory is referred to as the "original" memory.
In order to display a portion of a structure, the first step is segmentation. Those voxels or memory words belonging to the portion of the structure to be displayed are separated from those that are not to be shown. Such segmentation may consist in sorting the memory words as a function of the value of the information stored therein. For example, if the value lies within a value window or if it is less than or greater than a threshold, then the corresponding memory word (and thus the corresponding voxel) may be considered as belonging to the portion to be displayed. In this case a binary flag is additionally associated therewith: in one example, the voxel is associated with binary value 1. Otherwise the memory word is said not to belong to the structure and its flag is given the complementary binary value: e.g., 0. A memory word is now defined by its address, the value of the physical magnitude(s) measured at the location of the corresponding voxel, and a binary flag, binary 1 or binary 0, indicating whether or not the corresponding voxel is considered as belonging to the portion to be shown of the structure.
The display operation consists of displaying the image of the structure, i.e. in scanning all of the various memory words in the original memory as a function of an observation direction. A test is made to see whether or not these memory words belong to the portion to be shown and whether or not they are situated on the surface of this portion. They are then displayed or not, as appropriate in the image. Various methods are known for performing this operation. The best known method which also has the reputation of providing the highest processing performance in real time, is the method known as being of the Octree type. An implementation of this method is described in U.S. Pat. No. 4,719,585. Once segmentation has been performed, this method proceeds with a preliminary operation of subdividing the structure into eight subassemblies each having an additional binary flag allocated thereto. This binary flag has value 1 when all of the voxels of the subassembly are taken to belong to the portion of the structure to be displayed. If none of the voxels of the subassembly belong to said portion, then the subassembly is given binary value 0. However, if the subassembly includes both types of voxels, then it is itself subdivided into eight sub-subassemblies. This procedure is continued until all of the subassemblies and sub-subassemblies in a hierarchical organization are provided with an additional binary flag taking the value 0 or 1. In some cases, this hierarchical subdivision may come down to the level of individual voxels.
Once the subdivision has been done, an investigation is performed to discover which subassemblies or sub-subassemblies are visible from a given observation point. The advantage provided by this method of hierarchical subdivision is that the addresses of the memory words corresponding to the voxels situated on the surface are known automatically. The method thus deals immediately with voxels that are visible. The voxels thus merely need to be shown in the image, taking account of the display angle. It can thus be shown in one example of an original memory comprising 256.times.256.times.88 memory words, that it is possible to extract an image of a view of a portion of the structure described in this memory in about 0.5 seconds.
However, the drawback of the method as described above is that in order to calculate display effects, it requires specially-programmed machines having large amounts of computing power. Using specially-programmed machines come down to making equipment that can never be as cheap as universal type equipment operating in the standard manner. The development of this method is thus special-purpose and expensive.
In this method as in other methods known elsewhere (ray tracing, surface listing), once it has been determined which memory word corresponds to a voxel to be shown, it is necessary to calculate the coordinates of a position on a display screen where light information is to be made visible corresponding to the physical magnitude contained in the voxel. Calculating the coordinates of positions on a screen is the same as calculating the point of intersection with a plane (the plane of the screen) of a ray going away from the selected voxel in the display direction. The general display direction is normally perpendicular to the screen. Such algebraic type calculation is per se simple. It requires the coefficients of three director lines to be calculated representing the display direction: i.e. lines which are associated with the reference axis of the object in the reference system of the screen. These coefficients then appear as multiplying coefficients in the algebraic calculation of the coordinates of the selected voxel, or, equivalently, of the address of the corresponding memory word in the original memory.
In other words, for each voxel selected for display, there are three multiplications to be performed to determine its X position on the screen, there are three multiplications to be performed to determine its Y position on the screen, and there are three additions to be performed in both cases to take account of the origin being offset. All of these calculations, and in particular the multiplications, take far too long to perform and give rise to losses of time that prevent the image being shown quickly. These losses of time can only be avoided by making special processors whose lack of flexibility is described elsewhere.
Dynamic screen methods are described in the following articles:
1. "A dynamic screen technique for shaded graphics display of slice-represented objects", R. Anthony Reynolds, Dan Gordon, Lih-Shyang Chen, Computer Vision, Graphics and Image Processing 38, 257-298 (1987); and PA1 2. "Representation, display and manipulation of 3D digital scenes and their medical applications", Lih-Shyang Chen, Marc R. Sontag, Computer vision, Graphics and Image Processing 48, 190-216 (1989).
These methods proceed by projecting segments describing the object onto the screen. These dynamic screen methods consist of inserting each segment projected onto the screen as required amongst the set of segments that have already been projected. If such an insertion discovers new non-hidden pixels, these are painted with a gray level. These methods therefore do not use an intermediate memory of pointers pointing to the voxels of the object, as described below when describing the present invention. In the invention, hidden portions are eliminated by a conventional Z-buffer technique. However the advantage of the intermediate memory is to make it possible to paint the selected pixels by various techniques (in particular by using pre-calculated normals). The method described in the articles in question is constrained to use a technique of shading on the fly, which is of lower quality (cf. article 1, page 281). For performance reasons, to implement their algorithm, the authors make use of a "run length" type description similar to the "path length" description of the invention, (article 1, page 285). In this context, they cite Merrill, Updata and Trivedi (cf. the list of references in article 1).
Article 2 goes over the same ground as the first article so far as the present invention is concerned, but it describes the object by a method combining the use of a quadtree and a "run-length" description. The drawbacks of these methods are likewise excessive computation time.
An object of the invention is to remedy these drawbacks, in particular by eliminating all operations of the multiplication type and by calculating an address on the screen by making use of a previously-calculated address for another point on the screen. It is then shown that the multiplication operations required for display purposes can be reduced merely to performing additions using values known in advance, which is much simpler than performing multiplications. This technique can thus only be envisaged when scanning the original memory in a sequential scanning mode proper to the original memory. In practice, this scanning mode is one in which all the points of a line are scanned, all the lines of a plane are scanned, and all the planes of the image are scanned, one after another. This sequential type proper scanning mode in association with multiplications being made pointless already leads to a considerable saving in time. According to the invention, when using a proper scanning mode of this type, it is possible to recall previously-calculated coordinates for positions on the screen which correspond to previously studied voxels. Then, when going from one voxel to an adjacent voxel, it is possible to increment the coordinates on the screen as a function of the observation direction.
In order to recall previously-calculated addresses on the screen, it is preferable to make use of an additional memory referred to as a "pointer" memory. In this pointer memory, also referred to as the "pointer", each pointer word has an address corresponding to the coordinates of a position on the screen and contains information which corresponds to an address of an original memory word in the original memory.
When it is desired to display the image, it then becomes very simple to read all of the words in the pointer one after another so that the addresses of these words follow one another in the expected order of image elements or pixels on the screen. In other words, when making a display, each pixel along a line is read and all the lines are read one after another, simultaneously on the screen and in the pointer memory. Reading each new word in the pointer gives information concerning the address of an original memory word in the original memory. The information contained in this original memory word is then read. This information is used as the display magnitude, e.g. chrominance or luminance, so that a light point can be displayed on the screen.
In addition, in order to avoid processing all of the voxels that do not correspond to the portion of the structure that is to be displayed, the binary representation of the structure obtained during segmentation is transformed into a "path-length" representation. The purpose of this transformation is to accelerate calculation of the coordinates of positions on the screen since the calculation then concerns the projection of only those voxels that belong to the portion to be displayed.
The sole purpose of all of these operations is merely to select those voxels which are visible in the image to be displayed, i.e. those which are situated on the surface of the portion of the structure to be displayed. A subsequent shading operation, identical to prior art shading operations, is then used to process the visible points to take account of the observation direction. Various types of shading technique can be used, e.g. the type described in "Image quality in voxel base surface shading", A. Pommert, U. Tiede, G. Wiebecke, K. H. Hohne, Proceedings CAR '89, page 737, Springer-Verlag.